La Tua Missione 🎯
Riconnetti $N$ pianeti, dati come coordinate 2D, con una rete di "Hyper-lane" dal costo minimo.
- Obiettivo: Collega tutti i $N$ pianeti (vertici) in modo che siano tutti raggiungibili (direttamente o indirettamente).
- Obiettivo: Trova il progetto della rete che minimizza il **costo totale**.
Analisi 🛰️
Il costo di un'iperscansione (arco) è la distanza euclidea:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Un'iperscansione può essere costruita tra qualunquedue pianeti.
- Ciò significa che abbiamo un grafico completo (denso).
La Soluzione ⚙️
Questo è un classico problema di Albero Ricoprente Minimo (MST) problema.
- Algoritmo: L'indicazione suggerisce l'algoritmo di Prim (la versione $O(V^2)$), ideale per grafi densi).
- Punto di Partenza: Inizieremo l'algoritmo da Pianeta 0 per ottenere un risultato coerente.
Un grafo completo (sinistra) contiene tutti gli archi possibili. L'MST (destra) è il sottoinsieme più economico di archi che collega tutti i vertici.